\chapter{Busqueda heurística (informada)}

\section{Construicción de la función de búsqueda}
Esta tarea consiste en modificar el algoritmo realizado en la tarea 3 para incorporar la estrategia heurística A*.

Para esto se procederá a modificar el algoritmo de la tarea 3 del siguiente modo:
\begin{enumerate}
	\item Incorporar como estrategia nueva A*
	\item Definir f de un nodo f=costo+heurística.
	\item Posibilitar la elección de 2 heurística:
		\begin{itemize}
			\item Distancia euclídea de la posición actual a la final.
			\item Distancia manhattan de la posición actual a la final.
		\end{itemize}
\end{enumerate}

Considerar que el valor de la heurística está realizado con piezas rectas con el nivel mínimo de altura (grises). Esto es, que si la distancia medida en términos de posiciones (x,y) es un número d, el valor de la heurística será el de colocar d piezas rectas en lugares de mínimo nivel de gris.


Realizar 2 pruebas completas con las dos heurísticas, comprobar cual es mejor y que el resultado coincide en ambas.

Realizar la misma prueba con la estrategia de costo uniforme, comprobar que la solución es la misma y que su eficiencia es menor que la de A* con cualquier heurística.

\newpage

\section{Código Fuente}
\lstinputlisting[title=Algoritmo A*,language=Java]{src/A.java}

\newpage

\section{Resultados Obtenidos}
Se han realizado dos ejemplos con este código.
\lstinputlisting[title=Main,language=Java]{src/MainA.java}
\newpage
Y se han obtenido estos resultados
\lstinputlisting[title=Resultados]{src/pruebas/salidaA}


\subsection{Comparación de estrategias}
\begin{center}
\begin{tabular}{|c|c|c|c|}
	\hline
									& {\bf A* (d. Euclídea)}	& {\bf A* (d. Manhattan)}	& {\bf Costo Uniforme}	\\
	\hline
		{\bf Imagen 10x10}	& 2.42							& 4.16							& 11.082						\\
	\hline
		{\bf Imagen 15x15}	& 68.003							& 70.72							& 60.391						\\
	\hline
\end{tabular}
\end{center}

Como podemos ver al comparar ambas heurísticas, al tomar la distancia Euclídea siempre obtenemos un mejor tiempo que si cogemos la distancia Manhattan, obteniendo el mismo resultado.

Del mismo modo ambas heurísticas superan a la estrategia de Costo Uniforme en el ejemplo de 10x10. Pero no en el de 15x15. Esto puede ser debido a que tanto la estrategia en anchura, como la estrategia de Costo Uniforme tienen una mejora añadida en la entrega 3, que consiste en no seguir por caminos en los que el coste supere a la mejor solución encontrada hasta el momento.
